{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of K-Free Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTheNumOfKFreeSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计 K-Free 子集的总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含 <strong>无重复</strong> 元素的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果一个子集中 <strong>不</strong> 存在两个差的绝对值等于 <code>k</code> 的元素，则称其为 <strong>k-Free</strong> 子集。注意，空集是一个 <strong>k-Free</strong> 子集。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中 <strong>k-Free</strong> 子集的数量。</p>\n",
    "\n",
    "<p>一个数组的 <strong>子集</strong> 是该数组中的元素的选择（可能为零个）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,4,6], k = 1\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>有 5 个合法子集：{}, {5}, {4}, {6} 和 {4, 6} 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,5,8], k = 5\n",
    "<b>输出：</b>12\n",
    "<b>解释：</b>有12个合法子集：{}, {2}, {3}, {5}, {8}, {2, 3}, {2, 3, 5}, {2, 5}, {2, 5, 8}, {2, 8}, {3, 5} 和 {5, 8} 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [10,5,9,11], k = 20\n",
    "<b>输出：</b>16\n",
    "<b>解释：</b>所有的子集都是有效的。由于子集的总数为 24 = 16，因此答案为 16 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-k-free-subsets](https://leetcode.cn/problems/count-the-number-of-k-free-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-k-free-subsets](https://leetcode.cn/problems/count-the-number-of-k-free-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,6]\\n1', '[2,3,5,8]\\n5', '[10,5,9,11]\\n20']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fib = [1,2]\n",
    "for i in range(49):\n",
    "    fib.append(fib[-1] + fib[-2])\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        z = defaultdict(lambda: [])\n",
    "        for num in nums:\n",
    "            p = num % k\n",
    "            q = num // k\n",
    "            z[p].append(q)\n",
    "        ret = 1\n",
    "        for t in z.values():\n",
    "            t.sort()\n",
    "            last = -1\n",
    "            count = 0\n",
    "            for i in t:\n",
    "                if i == last + 1:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    ret *= fib[count]\n",
    "                    count = 1\n",
    "                last = i\n",
    "            ret *= fib[count]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        groups = defaultdict(list)\n",
    "        for num in nums:\n",
    "            groups[num % k].append(num)\n",
    "        ans = 1\n",
    "        for group in groups.values():\n",
    "            dp = [0] * len(group)\n",
    "            dp[0] = 2\n",
    "            for j in range(1, len(group)):\n",
    "                if group[j] - group[j-1] == k:\n",
    "                    dp[j] = dp[j-1] + dp[j-2] if j > 1 else dp[j-1] + 1\n",
    "                else:\n",
    "                    dp[j] = 2 * dp[j-1]\n",
    "            ans *= dp[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        groups = defaultdict(list)\n",
    "        for num in nums:\n",
    "            groups[num%k].append(num)\n",
    "        \n",
    "        ans = 1\n",
    "        for group in groups.values():\n",
    "            dp = [0] * len(group)\n",
    "            dp[0] = 2\n",
    "            for j in range(1, len(group)):\n",
    "                if group[j] - group[j-1] == k:\n",
    "                    dp[j] = dp[j-1] + dp[j-2] if j > 1 else dp[j-1] + 1\n",
    "                else:\n",
    "                    dp[j] = 2 *dp[j-1]\n",
    "            ans *= dp[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 2597的重复/相似题目\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "\n",
    "            ans *= f[m]\n",
    "\n",
    "        return ans  # 不-1 不需去掉空集\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        groups = defaultdict(list)\n",
    "        for num in nums:\n",
    "            groups[num%k].append(num)\n",
    "\n",
    "        ans = 1\n",
    "        for group in groups.values():\n",
    "            dp = [0] * len(group)\n",
    "            dp[0] = 2\n",
    "            for j in range(1, len(group)):\n",
    "                if group[j] - group[j-1] == k:\n",
    "                    dp[j] = dp[j-1] + dp[j-2] if j > 1 else dp[j-1] + 1\n",
    "                else:\n",
    "                    dp[j] = 2*dp[j-1]\n",
    "            ans *= dp[-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        groups = defaultdict(list)\n",
    "        for num in nums:\n",
    "            groups[num%k].append(num)\n",
    "        \n",
    "        ans = 1\n",
    "        # dp表示子集的个数\n",
    "        for group in groups.values():\n",
    "            dp = [0]*len(group)\n",
    "            dp[0] = 2\n",
    "            for j in range(1, len(group)):\n",
    "                if group[j] - group[j-1]  == k:\n",
    "                    dp[j] = dp[j-1] + dp[j-2] if j > 1 else dp[j-1] + 1\n",
    "                else:\n",
    "                    dp[j] = 2 * dp[j-1]\n",
    "            ans *= dp[-1]\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        groups = defaultdict(list)\n",
    "        for num in nums:\n",
    "            groups[num%k].append(num)\n",
    "        ans = 1\n",
    "        for group in groups.values():\n",
    "            dp = [0]*len(group)\n",
    "            dp[0] = 2\n",
    "            for i in range(1, len(group)):\n",
    "                if group[i] - group[i-1] == k:\n",
    "                    dp[i] = dp[i-1] + dp[i-2] if i > 1 else dp[i-1] + 1\n",
    "                else:\n",
    "                    dp[i] = 2 * dp[i-1]\n",
    "            ans *= dp[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x in nums:\n",
    "            g[x%k].append(x // k)\n",
    "        ans = 1\n",
    "        for v in g.values():\n",
    "            v = sorted([-2] + v)\n",
    "            n = len(v)\n",
    "            dp = [1] * n\n",
    "            for i in range(1, n):\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if v[j] + 1 != v[i]:\n",
    "                        dp[i] = dp[j] + dp[i-1]\n",
    "                        break\n",
    "            ans *= dp[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:\n",
    "        groups = defaultdict(Counter)\n",
    "        for x in nums:\n",
    "            groups[x % k][x] += 1\n",
    "\n",
    "        ans = 1\n",
    "        for cnt in groups.values():\n",
    "            g = sorted(cnt.items())\n",
    "            m = len(g)\n",
    "            f = [0] * (m + 1)\n",
    "            f[0] = 1\n",
    "            f[1] = 1 << g[0][1]\n",
    "            for i in range(1, m):\n",
    "                if g[i][0] - g[i - 1][0] == k:\n",
    "                    f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)\n",
    "                else:\n",
    "                    f[i + 1] = f[i] << g[i][1]\n",
    "\n",
    "            ans *= f[m]\n",
    "\n",
    "        return ans  # 不-1 不需去掉空集"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
